import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class TopK {
    /*
    * 求数组中的前 k 个 最小元素
    * @param array
    * @param  k
    * @return
    * */
    public static int[] topK(int[] array,int k){
        // 创建一个大小为 k 的 大根堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for(int i = 0;i <array.length;i++){
            if(maxHeap.size() < k){
                maxHeap.offer(array[i]);
            }else{
                // 从第 k + 1 个元素开始，每个元素都要和 堆顶元素进行比较。
                // 如果 比 堆顶元素小，则与堆顶元素交换，
                int top = maxHeap.peek();
                if(top > array[i]){
                    maxHeap.poll();// 先将堆顶元素弹出，优先级队列会自行调整一下
                    maxHeap.offer(array[i]);// 后面入队也是一样，也会自行调整一下
                }
            }
        }
        // 此时 maxHeap 堆里，存储的是 前 k  个最小的 值
        // 现在要做的是 将其 转换称是数组，返回
        int[] tmp =  new int[k];
        for(int i = 0;i < k;i++){
            tmp[i] = maxHeap.poll();
        }
        return tmp;
    }

    public static void main(String[] args) {
        int[] array = {18,21,8,10,34,12};
        int[] tmp =topK(array,3);// 求前三个最小值
        System.out.println(Arrays.toString(tmp));
    }
}
